package SortTemplate;
/*
大根堆
 */
public class MaxHeap {

    public static final int MaxData = 99999;  // 定义哨兵的值
    int[] data;            // 储存堆元素的数组
    int size;              // 堆的当前元素的个数
    int capacity;          // 堆的最大容量


    public MaxHeap create(int MaxSize) {
        MaxHeap maxHeap = new MaxHeap();
        maxHeap.data = new int[MaxSize * MaxSize];
        maxHeap.size = 0;
        maxHeap.capacity = MaxSize;
        maxHeap.data[0] = MaxData;    // 建立哨兵，方便操作
        return maxHeap;
    }

    public boolean IsFull(MaxHeap H) {
        return H.size == H.capacity;
    }

    public boolean IsEmpty(MaxHeap H) {
        return H.size == 0;
    }


    public void insert(MaxHeap H, int item) {
        if(IsFull(H)) {
            // System.out.println("最大堆已满");
            return;
        }
        int i = ++H.size;    //i指向插入元素后堆中最后一个元素的位置
        //这里利用堆(完全二叉树)的性质,每个子节点i/2必定得到父节点。称为向下过滤节点
        for( ; H.data[i/2] < item; i/=2) {
            H.data[i] = H.data[i/2];
        }
        H.data[i] = item;
    }

    public int deleteMax(MaxHeap H) {
        int parent, child;
        int MaxItem, temp;
        if (IsEmpty(H)) {
            System.out.println("最大堆已空");
            return 0;
        }
        MaxItem = H.data[1];
        temp = H.data[H.size--];
        // parent*2<H.size说明有儿子(左右至少一个)
        for (parent = 1; parent * 2 < H.size; parent = child) {
            child = parent * 2;   //假设左儿子为最大值
            // child != H.size说明有右儿子,H.data[child]<H.data[child+1]右儿子更大
            if ((child != H.size) && (H.data[child] < H.data[child + 1])) {
                child++;
            }
            if (temp >= H.data[child]) {
                break;
            } else {
                H.data[parent] = H.data[child];
            }
        }
        H.data[parent] = temp;
        return MaxItem;
    }
}
